`
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function (preorder, postorder) {
  // 存储 postorder 中值到索引的映射
  const valToIndex = {};
  for (let i = 0; i < postorder.length; i++) {
    valToIndex[postorder[i]] = i;
  }

  function build(
    preorder, preStart, preEnd,
    postorder, postStart, postEnd
  ) {
    if (preStart > preEnd) {
      return null;
    }
    if (preStart === preEnd) {
      return new TreeNode(preorder[preStart]);
    }

    // root 节点对应的值就是前序遍历数组的第一个元素
    const rootVal = preorder[preStart];
    // root.left 的值是前序遍历第二个元素
    // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
    // 确定 preorder 和 postorder 中左右子树的元素区间
    const leftRootVal = preorder[preStart + 1];
    // leftRootVal 在后序遍历数组中的索引
    const index = valToIndex[leftRootVal];
    // 左子树的元素个数
    const leftSize = index - postStart + 1;

    // 先构造出当前根节点
    const root = new TreeNode(rootVal);

    // 递归构造左右子树
    // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
    // 这里传递的参数可参考 https://labuladong.online/algo/images/binary-tree-ii/8.jpeg
    root.left = build(
      preorder, preStart + 1, preStart + leftSize,
      postorder, postStart, index
    );
    root.right = build(
      preorder, preStart + leftSize + 1, preEnd,
      postorder, index + 1, postEnd - 1
    );

    return root;
  };

  return build(
    preorder, 0, preorder.length - 1,
    postorder, 0, postorder.length - 1
  )
};